package com.kingwood.algorithm.test;

import java.util.*;

/**
 * @Author 22025812
 * @Description: TODO
 * @Date: 2024/2/29 13:49
 * @Modified By：
 * @Version 1.0
 */
public class TanXin {

    /**
     * 分披萨
     * https://fcqian.blog.csdn.net/article/details/134793989
     * @param cakes
     * @return
     */
    public static int getMaxCake(int[] cakes) {
        int ans = 0;

        return ans;
    }

    public static String largestNumber(int[] nums) {
        int n = nums.length;
        String[] strs = new String[n];

        for (int i=0; i<n; i++) {
            strs[i] = String.valueOf(nums[i]);
        }

        Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));

        if (strs[0].equals("0") || strs[0].startsWith("0")) {
            return "0";
        }

        StringBuilder sb = new StringBuilder();
        for (String s : strs) {
            sb.append(s);
        }

        return sb.toString();
    }

    /**
     * 吃橘子
     * @return
     */
    static HashMap<Integer, Integer> dp = new HashMap<>();
    public static int minDays(int n) {
        if (n <= 1) {
            return n;
        }

        if (dp.containsKey(n)) {
            return dp.get(n);
        }

        int ans = Math.min(n%2 +1 + minDays(n/2), n%3+1 + minDays(n/3));
        dp.put(n, ans);
        return ans;
    }

    /**
     * 需要多少会议室，和最多线段重合问题一致
     * @param meeting
     * @return
     */
    public static int minMeetingRooms(int[][] meeting) {
        int n = meeting.length;
        // 先根据开始时间升序排序
        Arrays.sort(meeting, (a, b) -> a[0] - b[0]);

        // 默认从小到大排序的
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int ans = 0;

        for (int i=0; i<n; i++) {
            while (!heap.isEmpty() && heap.peek() <= meeting[i][0]) {
                heap.poll();
            }

            heap.add(meeting[i][1]);
            ans = Math.max(ans, heap.size());
        }

        return ans;
    }

    /**
     * https://blog.csdn.net/qfc_128220/article/details/134939442
     * 会议室占用时间
     * @param rootTimes
     * @return
     */
    public static int[][] mergeRooting(int[][] rootTimes) {
        // 根据会议开始时间升序排序
        Arrays.sort(rootTimes, (a, b) -> a[0] - b[0]);

        ArrayList<int[]> list = new ArrayList<>();

        // 上一个会议占用时间端
        int[] pre = rootTimes[0];
        for (int i=1; i<rootTimes.length; i++) {
            // 当前会议占用时间
            int [] cur = rootTimes[i];

            if (cur[0] <= pre[1]) {
                // 当前会议开始时间小于等于上一个会议结束时间，两个会议合并
                // 注意合并时，
                pre[1] = Math.max(pre[1], cur[1]);
            } else {
                // 否则不可以合并
                list.add(pre);
                pre = cur;
            }
        }

        list.add(pre);
        return list.toArray(new int[0][]);
    }

    /**
     * 小朋友来自多少小区
     * https://fcqian.blog.csdn.net/article/details/135119311
     * 本题的输出其实是至少的小朋友数量，而不是班级小朋友至少来自几个小区。
     * 原题有误，应该是至少有多少个小朋友。
     * @param arr
     * @return
     */
    public static int sumOfLitteFriends(int[] arr) {
        HashMap<Integer, Integer> cnts = new HashMap<>();
        for (int i=0; i<arr.length; i++) {
            int num = cnts.getOrDefault(arr[i], 0);
            cnts.put(arr[i], num+1);
        }

        int ans = 0;
        for (int key : cnts.keySet()) {
            int total = key + 1;
            int sep = (int) Math.ceil(cnts.get(key) * 1.0 / total);
            int minSum = sep * total;
            ans += minSum;
        }

        return ans;
    }

    public static int connectSticks(int[] arr) {
        if (arr == null || arr.length <= 0) {
            return 0;
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i=0; i<arr.length; i++) {
            pq.offer(arr[i]);
        }

        int sum = 0;
        int cur = 0;
        while (pq.size() > 1) {
            cur = pq.poll() + pq.poll();
            sum += cur;
            pq.offer(cur);
        }

        return sum;
    }

    public static void main(String[] args) {
        System.out.println(3/5);
//        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//
//        int[][] roomTimes = new int[n][2];
//        for (int i=0; i<n; i++) {
//            roomTimes[i][0] = scanner.nextInt();
//            roomTimes[i][1] = scanner.nextInt();
//        }
//
//        int[][] res = mergeRooting(roomTimes);
//        for (int[] times : res) {
//            System.out.println(times[0] + " " + times[1]);
//        }

//        int[] arr = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
//        int ans = sumOfLitteFriends(arr);
//        System.out.println(ans);
    }
}
